/**
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * https://leetcode.cn/problems/chou-shu-lcof/
 */
class NthUglyNumber {
    public int nthUglyNumber(int n) {
        int[] arr={2,3,5};
        Set<Long> set=new HashSet<>();
        PriorityQueue<Long> minHeap=new PriorityQueue<>();
        set.add(1L);
        minHeap.offer(1L);
        int ugly=0;
        for(int i=0;i<n;i++){
            long cur=minHeap.poll();
            ugly=(int)cur;
            for(int num:arr){
                long next=cur*num;
                if(set.add(next)){
                    minHeap.offer(next);
                    
                }
            }
        }
        return ugly;
    }
}